public class Solution60 {
    public String getPermutation(int n, int k) {
        k=k-1;
        int[] mul=new int[]{1,1,2,6,24,120,720,5040,40320,362880};
        StringBuilder stringBuilder=new StringBuilder();
        int[] f=new int[10];
        for (int i=1;i<=n;i++){
            f[i]=1;
        }
        for (int i=1;i<=n;i++){
            stringBuilder.append(get(f,k/mul[n-i]+1,n));
            k=k%mul[n-i];
        }
        return stringBuilder.toString();
    }

    private int get(int[] f, int i,int n) {
        int count=0;
        for (int j=1;j<=n;j++){
            if (f[j]==1){
                count++;
                if (count==i){
                    f[j]=0;
                    return j;
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(new Solution60().getPermutation(4,9));
    }
}
